(function() {
	d3.layout = {};
	// Implements hierarchical edge bundling using Holten's algorithm. For each
	// input link, a path is computed that travels through the tree, up the parent
	// hierarchy to the least common ancestor, and then back down to the destination
	// node. Each path is simply an array of nodes.
	d3.layout.bundle = function() {
		return function(links) {
			var paths = [], i = -1, n = links.length;
			while(++i < n)
			paths.push(d3_layout_bundlePath(links[i]));
			return paths;
		};
	};
	function d3_layout_bundlePath(link) {
		var start = link.source, end = link.target, lca = d3_layout_bundleLeastCommonAncestor(start, end), points = [start];
		while(start !== lca) {
			start = start.parent;
			points.push(start);
		}
		var k = points.length;
		while(end !== lca) {
			points.splice(k, 0, end);
			end = end.parent;
		}
		return points;
	}

	function d3_layout_bundleAncestors(node) {
		var ancestors = [], parent = node.parent;
		while(parent != null) {
			ancestors.push(node);
			node = parent;
			parent = parent.parent;
		}
		ancestors.push(node);
		return ancestors;
	}

	function d3_layout_bundleLeastCommonAncestor(a, b) {
		if(a === b)
			return a;
		var aNodes = d3_layout_bundleAncestors(a), bNodes = d3_layout_bundleAncestors(b), aNode = aNodes.pop(), bNode = bNodes.pop(), sharedNode = null;
		while(aNode === bNode) {
			sharedNode = aNode;
			aNode = aNodes.pop();
			bNode = bNodes.pop();
		}
		return sharedNode;
	}


	d3.layout.chord = function() {
		var chord = {}, chords, groups, matrix, n, padding = 0, sortGroups, sortSubgroups, sortChords;

		function relayout() {
			var subgroups = {}, groupSums = [], groupIndex = d3.range(n), subgroupIndex = [], k, x, x0, i, j;
			chords = [];
			groups = [];

			// Compute the sum.
			k = 0, i = -1;
			while(++i < n) { x = 0, j = -1;
				while(++j < n) {
					x += matrix[i][j];
				}
				groupSums.push(x);
				subgroupIndex.push(d3.range(n));
				k += x;
			}

			// Sort groups…
			if(sortGroups) {
				groupIndex.sort(function(a, b) {
					return sortGroups(groupSums[a], groupSums[b]);
				});
			}

			// Sort subgroups…
			if(sortSubgroups) {
				subgroupIndex.forEach(function(d, i) {
					d.sort(function(a, b) {
						return sortSubgroups(matrix[i][a], matrix[i][b]);
					});
				});
			}

			// Convert the sum to scaling factor for [0, 2pi].
			// TODO Allow start and end angle to be specified.
			// TODO Allow padding to be specified as percentage?
			k = (2 * Math.PI - padding * n) / k;

			// Compute the start and end angle for each group and subgroup.
			// Note: Opera has a bug reordering object literal properties!
			x = 0, i = -1;
			while(++i < n) { x0 = x, j = -1;
				while(++j < n) {
					var di = groupIndex[i], dj = subgroupIndex[di][j], v = matrix[di][dj], a0 = x, a1 = x += v * k;
					subgroups[di + "-" + dj] = {
						index : di,
						subindex : dj,
						startAngle : a0,
						endAngle : a1,
						value : v
					};
				}
				groups.push({
					index : di,
					startAngle : x0,
					endAngle : x,
					value : (x - x0) / k
				});
				x += padding;
			}

			// Generate chords for each (non-empty) subgroup-subgroup link.
			i = -1;
			while(++i < n) {
				j = i - 1;
				while(++j < n) {
					var source = subgroups[i + "-" + j], target = subgroups[j + "-" + i];
					if(source.value || target.value) {
						chords.push(source.value < target.value ? {
							source : target,
							target : source
						} : {
							source : source,
							target : target
						});
					}
				}
			}

			if(sortChords)
				resort();
		}

		function resort() {
			chords.sort(function(a, b) {
				return sortChords((a.source.value + a.target.value) / 2, (b.source.value + b.target.value) / 2);
			});
		}


		chord.matrix = function(x) {
			if(!arguments.length)
				return matrix;
			n = ( matrix = x) && matrix.length;
			chords = groups = null;
			return chord;
		};

		chord.padding = function(x) {
			if(!arguments.length)
				return padding;
			padding = x;
			chords = groups = null;
			return chord;
		};

		chord.sortGroups = function(x) {
			if(!arguments.length)
				return sortGroups;
			sortGroups = x;
			chords = groups = null;
			return chord;
		};

		chord.sortSubgroups = function(x) {
			if(!arguments.length)
				return sortSubgroups;
			sortSubgroups = x;
			chords = null;
			return chord;
		};

		chord.sortChords = function(x) {
			if(!arguments.length)
				return sortChords;
			sortChords = x;
			if(chords)
				resort();
			return chord;
		};

		chord.chords = function() {
			if(!chords)
				relayout();
			return chords;
		};

		chord.groups = function() {
			if(!groups)
				relayout();
			return groups;
		};
		return chord;
	};
	// A rudimentary force layout using Gauss-Seidel.
	d3.layout.force = function() {
		var force = {}, event = d3.dispatch("tick"), size = [1, 1], drag, alpha, friction = .9, linkDistance = d3_layout_forceLinkDistance, linkStrength = d3_layout_forceLinkStrength, charge = -30, gravity = .1, theta = .8, interval, nodes = [], links = [], distances, strengths, charges;

		function repulse(node) {
			return function(quad, x1, y1, x2, y2) {
				if(quad.point !== node) {
					var dx = quad.cx - node.x, dy = quad.cy - node.y, dn = 1 / Math.sqrt(dx * dx + dy * dy);

					/* Barnes-Hut criterion. */
					if((x2 - x1) * dn < theta) {
						var k = quad.charge * dn * dn;
						node.px -= dx * k;
						node.py -= dy * k;
						return true;
					}

					if(quad.point && isFinite(dn)) {
						var k = quad.pointCharge * dn * dn;
						node.px -= dx * k;
						node.py -= dy * k;
					}
				}
				return !quad.charge;
			};
		}

		function tick() {
			var n = nodes.length, m = links.length, q, i, // current index
			o, // current object
			s, // current source
			t, // current target
			l, // current distance
			k, // current force
			x, // x-distance
			y;
			// y-distance

			// gauss-seidel relaxation for links
			for( i = 0; i < m; ++i) {
				o = links[i];
				s = o.source;
				t = o.target;
				x = t.x - s.x;
				y = t.y - s.y;
				if( l = (x * x + y * y)) {
					l = alpha * strengths[i] * (( l = Math.sqrt(l)) - distances[i]) / l;
					x *= l;
					y *= l;
					t.x -= x * ( k = s.weight / (t.weight + s.weight));
					t.y -= y * k;
					s.x += x * ( k = 1 - k);
					s.y += y * k;
				}
			}

			// apply gravity forces
			if( k = alpha * gravity) {
				x = size[0] / 2;
				y = size[1] / 2;
				i = -1;
				if(k)
					while(++i < n) {
						o = nodes[i];
						o.x += (x - o.x) * k;
						o.y += (y - o.y) * k;
					}
			}

			// compute quadtree center of mass and apply charge forces
			if(charge) {
				d3_layout_forceAccumulate( q = d3.geom.quadtree(nodes), alpha, charges);
				i = -1;
				while(++i < n) {
					if(!( o = nodes[i]).fixed) {
						q.visit(repulse(o));
					}
				}
			}

			// position verlet integration
			i = -1;
			while(++i < n) {
				o = nodes[i];
				if(o.fixed) {
					o.x = o.px;
					o.y = o.py;
				} else {
					o.x -= (o.px - (o.px = o.x)) * friction;
					o.y -= (o.py - (o.py = o.y)) * friction;
				}
			}

			event.tick({
				type : "tick",
				alpha : alpha
			});

			// simulated annealing, basically
			return (alpha *= .99) < .005;
		}


		force.nodes = function(x) {
			if(!arguments.length)
				return nodes;
			nodes = x;
			return force;
		};

		force.links = function(x) {
			if(!arguments.length)
				return links;
			links = x;
			return force;
		};

		force.size = function(x) {
			if(!arguments.length)
				return size;
			size = x;
			return force;
		};

		force.linkDistance = function(x) {
			if(!arguments.length)
				return linkDistance;
			linkDistance = d3.functor(x);
			return force;
		};
		// For backwards-compatibility.
		force.distance = force.linkDistance;

		force.linkStrength = function(x) {
			if(!arguments.length)
				return linkStrength;
			linkStrength = d3.functor(x);
			return force;
		};

		force.friction = function(x) {
			if(!arguments.length)
				return friction;
			friction = x;
			return force;
		};

		force.charge = function(x) {
			if(!arguments.length)
				return charge;
			charge = typeof x === "function" ? x : +x;
			return force;
		};

		force.gravity = function(x) {
			if(!arguments.length)
				return gravity;
			gravity = x;
			return force;
		};

		force.theta = function(x) {
			if(!arguments.length)
				return theta;
			theta = x;
			return force;
		};

		force.start = function() {
			var i, j, n = nodes.length, m = links.length, w = size[0], h = size[1], neighbors, o;

			for( i = 0; i < n; ++i) {
				( o = nodes[i]).index = i;
				o.weight = 0;
			}
			distances = [];
			strengths = [];
			for( i = 0; i < m; ++i) {
				o = links[i];
				if( typeof o.source == "number")
					o.source = nodes[o.source];
				if( typeof o.target == "number")
					o.target = nodes[o.target];
				distances[i] = linkDistance.call(this, o, i);
				strengths[i] = linkStrength.call(this, o, i); ++o.source.weight; ++o.target.weight;
			}

			for( i = 0; i < n; ++i) {
				o = nodes[i];
				if(isNaN(o.x))
					o.x = position("x", w);
				if(isNaN(o.y))
					o.y = position("y", h);
				if(isNaN(o.px))
					o.px = o.x;
				if(isNaN(o.py))
					o.py = o.y;
			}
			charges = [];
			if( typeof charge === "function") {
				for( i = 0; i < n; ++i) {
					charges[i] = +charge.call(this, nodes[i], i);
				}
			} else {
				for( i = 0; i < n; ++i) {
					charges[i] = charge;
				}
			}

			// initialize node position based on first neighbor
			function position(dimension, size) {
				var neighbors = neighbor(i), j = -1, m = neighbors.length, x;
				while(++j < m)
				if(!isNaN( x = neighbors[j][dimension]))
					return x;
				return Math.random() * size;
			}

			// initialize neighbors lazily
			function neighbor() {
				if(!neighbors) {
					neighbors = [];
					for( j = 0; j < n; ++j) {
						neighbors[j] = [];
					}
					for( j = 0; j < m; ++j) {
						var o = links[j];
						neighbors[o.source.index].push(o.target);
						neighbors[o.target.index].push(o.source);
					}
				}
				return neighbors[i];
			}

			return force.resume();
		};

		force.resume = function() {
			alpha = .1;
			d3.timer(tick);
			return force;
		};

		force.stop = function() {
			alpha = 0;
			return force;
		};
		// use `node.call(force.drag)` to make nodes draggable
		force.drag = function() {
			if(!drag)
				drag = d3.behavior.drag().origin(Object).on("dragstart", dragstart).on("drag", d3_layout_forceDrag).on("dragend", d3_layout_forceDragEnd);

			this.on("mouseover.force", d3_layout_forceDragOver).on("mouseout.force", d3_layout_forceDragOut).call(drag);
		};
		function dragstart(d) {
			d3_layout_forceDragOver( d3_layout_forceDragNode = d);
			d3_layout_forceDragForce = force;
		}

		return d3.rebind(force, event, "on");
	};
	var d3_layout_forceDragForce, d3_layout_forceDragNode;

	function d3_layout_forceDragOver(d) {
		d.fixed |= 2;
	}

	function d3_layout_forceDragOut(d) {
		if(d !== d3_layout_forceDragNode)
			d.fixed &= 1;
	}

	function d3_layout_forceDragEnd() {
		d3_layout_forceDrag();
		d3_layout_forceDragNode.fixed &= 1;
		d3_layout_forceDragForce = d3_layout_forceDragNode = null;
	}

	function d3_layout_forceDrag() {
		d3_layout_forceDragNode.px = d3.event.x;
		d3_layout_forceDragNode.py = d3.event.y;
		d3_layout_forceDragForce.resume();
		// restart annealing
	}

	function d3_layout_forceAccumulate(quad, alpha, charges) {
		var cx = 0, cy = 0;
		quad.charge = 0;
		if(!quad.leaf) {
			var nodes = quad.nodes, n = nodes.length, i = -1, c;
			while(++i < n) {
				c = nodes[i];
				if(c == null)
					continue;
				d3_layout_forceAccumulate(c, alpha, charges);
				quad.charge += c.charge;
				cx += c.charge * c.cx;
				cy += c.charge * c.cy;
			}
		}
		if(quad.point) {
			// jitter internal nodes that are coincident
			if(!quad.leaf) {
				quad.point.x += Math.random() - .5;
				quad.point.y += Math.random() - .5;
			}
			var k = alpha * charges[quad.point.index];
			quad.charge += quad.pointCharge = k;
			cx += k * quad.point.x;
			cy += k * quad.point.y;
		}
		quad.cx = cx / quad.charge;
		quad.cy = cy / quad.charge;
	}

	function d3_layout_forceLinkDistance(link) {
		return 20;
	}

	function d3_layout_forceLinkStrength(link) {
		return 1;
	}


	d3.layout.partition = function() {
		var hierarchy = d3.layout.hierarchy(), size = [1, 1];
		// width, height

		function position(node, x, dx, dy) {
			var children = node.children;
			node.x = x;
			node.y = node.depth * dy;
			node.dx = dx;
			node.dy = dy;
			if(children && ( n = children.length)) {
				var i = -1, n, c, d;
				dx = node.value ? dx / node.value : 0;
				while(++i < n) {
					position( c = children[i], x, d = c.value * dx, dy);
					x += d;
				}
			}
		}

		function depth(node) {
			var children = node.children, d = 0;
			if(children && ( n = children.length)) {
				var i = -1, n;
				while(++i < n)
				d = Math.max(d, depth(children[i]));
			}
			return 1 + d;
		}

		function partition(d, i) {
			var nodes = hierarchy.call(this, d, i);
			position(nodes[0], 0, size[0], size[1] / depth(nodes[0]));
			return nodes;
		}


		partition.size = function(x) {
			if(!arguments.length)
				return size;
			size = x;
			return partition;
		};
		return d3_layout_hierarchyRebind(partition, hierarchy);
	};
	d3.layout.pie = function() {
		var value = Number, sort = d3_layout_pieSortByValue, startAngle = 0, endAngle = 2 * Math.PI;

		function pie(data, i) {

			// Compute the numeric values for each data element.
			var values = data.map(function(d, i) {
				return +value.call(pie, d, i);
			});
			// Compute the start angle.
			var a = +( typeof startAngle === "function" ? startAngle.apply(this, arguments) : startAngle);

			// Compute the angular scale factor: from value to radians.
			var k = (( typeof endAngle === "function" ? endAngle.apply(this, arguments) : endAngle) - startAngle) / d3.sum(values);

			// Optionally sort the data.
			var index = d3.range(data.length);
			if(sort != null)
				index.sort(sort === d3_layout_pieSortByValue ? function(i, j) {
					return values[j] - values[i];
				} : function(i, j) {
					return sort(data[i], data[j]);
				});
			// Compute the arcs!
			var arcs = index.map(function(i) {
				return {
					data : data[i],
					value : d = values[i],
					startAngle : a,
					endAngle : a += d * k
				};
			});
			// Return the arcs in the original data's order.
			return data.map(function(d, i) {
				return arcs[index[i]];
			});
		}

		/**
		 * Specifies the value function *x*, which returns a nonnegative numeric value
		 * for each datum. The default value function is `Number`. The value function
		 * is passed two arguments: the current datum and the current index.
		 */
		pie.value = function(x) {
			if(!arguments.length)
				return value;
			value = x;
			return pie;
		};
		/**
		 * Specifies a sort comparison operator *x*. The comparator is passed two data
		 * elements from the data array, a and b; it returns a negative value if a is
		 * less than b, a positive value if a is greater than b, and zero if a equals
		 * b.
		 */
		pie.sort = function(x) {
			if(!arguments.length)
				return sort;
			sort = x;
			return pie;
		};
		/**
		 * Specifies the overall start angle of the pie chart. Defaults to 0. The
		 * start angle can be specified either as a constant or as a function; in the
		 * case of a function, it is evaluated once per array (as opposed to per
		 * element).
		 */
		pie.startAngle = function(x) {
			if(!arguments.length)
				return startAngle;
			startAngle = x;
			return pie;
		};
		/**
		 * Specifies the overall end angle of the pie chart. Defaults to 2π. The
		 * end angle can be specified either as a constant or as a function; in the
		 * case of a function, it is evaluated once per array (as opposed to per
		 * element).
		 */
		pie.endAngle = function(x) {
			if(!arguments.length)
				return endAngle;
			endAngle = x;
			return pie;
		};
		return pie;
	};
	var d3_layout_pieSortByValue = {};
	// data is two-dimensional array of x,y; we populate y0
	d3.layout.stack = function() {
		var values = Object, order = d3_layout_stackOrders["default"], offset = d3_layout_stackOffsets["zero"], out = d3_layout_stackOut, x = d3_layout_stackX, y = d3_layout_stackY;

		function stack(data, index) {

			// Convert series to canonical two-dimensional representation.
			var series = data.map(function(d, i) {
				return values.call(stack, d, i);
			});
			// Convert each series to canonical [[x,y]] representation.
			var points = series.map(function(d, i) {
				return d.map(function(v, i) {
					return [x.call(stack, v, i), y.call(stack, v, i)];
				});
			});
			// Compute the order of series, and permute them.
			var orders = order.call(stack, points, index);
			series = d3.permute(series, orders);
			points = d3.permute(points, orders);

			// Compute the baseline…
			var offsets = offset.call(stack, points, index);

			// And propagate it to other series.
			var n = series.length, m = series[0].length, i, j, o;
			for( j = 0; j < m; ++j) {
				out.call(stack, series[0][j], o = offsets[j], points[0][j][1]);
				for( i = 1; i < n; ++i) {
					out.call(stack, series[i][j], o += points[i - 1][j][1], points[i][j][1]);
				}
			}

			return data;
		}


		stack.values = function(x) {
			if(!arguments.length)
				return values;
			values = x;
			return stack;
		};

		stack.order = function(x) {
			if(!arguments.length)
				return order;
			order = typeof x === "function" ? x : d3_layout_stackOrders[x];
			return stack;
		};

		stack.offset = function(x) {
			if(!arguments.length)
				return offset;
			offset = typeof x === "function" ? x : d3_layout_stackOffsets[x];
			return stack;
		};

		stack.x = function(z) {
			if(!arguments.length)
				return x;
			x = z;
			return stack;
		};

		stack.y = function(z) {
			if(!arguments.length)
				return y;
			y = z;
			return stack;
		};

		stack.out = function(z) {
			if(!arguments.length)
				return out;
			out = z;
			return stack;
		};
		return stack;
	}
	function d3_layout_stackX(d) {
		return d.x;
	}

	function d3_layout_stackY(d) {
		return d.y;
	}

	function d3_layout_stackOut(d, y0, y) {
		d.y0 = y0;
		d.y = y;
	}

	var d3_layout_stackOrders = {

		"inside-out" : function(data) {
			var n = data.length, i, j, max = data.map(d3_layout_stackMaxIndex), sums = data.map(d3_layout_stackReduceSum), index = d3.range(n).sort(function(a, b) {
				return max[a] - max[b];
			}), top = 0, bottom = 0, tops = [], bottoms = [];
			for( i = 0; i < n; ++i) {
				j = index[i];
				if(top < bottom) {
					top += sums[j];
					tops.push(j);
				} else {
					bottom += sums[j];
					bottoms.push(j);
				}
			}
			return bottoms.reverse().concat(tops);
		},
		"reverse" : function(data) {
			return d3.range(data.length).reverse();
		},
		"default" : function(data) {
			return d3.range(data.length);
		}
	};

	var d3_layout_stackOffsets = {

		"silhouette" : function(data) {
			var n = data.length, m = data[0].length, sums = [], max = 0, i, j, o, y0 = [];
			for( j = 0; j < m; ++j) {
				for( i = 0, o = 0; i < n; i++)
				o += data[i][j][1];
				if(o > max)
					max = o;
				sums.push(o);
			}
			for( j = 0; j < m; ++j) {
				y0[j] = (max - sums[j]) / 2;
			}
			return y0;
		},
		"wiggle" : function(data) {
			var n = data.length, x = data[0], m = x.length, max = 0, i, j, k, s1, s2, s3, dx, o, o0, y0 = [];
			y0[0] = o = o0 = 0;
			for( j = 1; j < m; ++j) {
				for( i = 0, s1 = 0; i < n; ++i)
				s1 += data[i][j][1];
				for( i = 0, s2 = 0, dx = x[j][0] - x[j - 1][0]; i < n; ++i) {
					for( k = 0, s3 = (data[i][j][1] - data[i][j - 1][1]) / (2 * dx); k < i; ++k) {
						s3 += (data[k][j][1] - data[k][j - 1][1]) / dx;
					}
					s2 += s3 * data[i][j][1];
				}
				y0[j] = o -= s1 ? s2 / s1 * dx : 0;
				if(o < o0)
					o0 = o;
			}
			for( j = 0; j < m; ++j)
			y0[j] -= o0;
			return y0;
		},
		"expand" : function(data) {
			var n = data.length, m = data[0].length, k = 1 / n, i, j, o, y0 = [];
			for( j = 0; j < m; ++j) {
				for( i = 0, o = 0; i < n; i++)
				o += data[i][j][1];
				if(o)
					for( i = 0; i < n; i++)
					data[i][j][1] /= o;
				else
					for( i = 0; i < n; i++)
					data[i][j][1] = k;
			}
			for( j = 0; j < m; ++j)
			y0[j] = 0;
			return y0;
		},
		"zero" : function(data) {
			var j = -1, m = data[0].length, y0 = [];
			while(++j < m)
			y0[j] = 0;
			return y0;
		}
	};

	function d3_layout_stackMaxIndex(array) {
		var i = 1, j = 0, v = array[0][1], k, n = array.length;
		for(; i < n; ++i) {
			if(( k = array[i][1]) > v) {
				j = i;
				v = k;
			}
		}
		return j;
	}

	function d3_layout_stackReduceSum(d) {
		return d.reduce(d3_layout_stackSum, 0);
	}

	function d3_layout_stackSum(p, d) {
		return p + d[1];
	}


	d3.layout.histogram = function() {
		var frequency = true, valuer = Number, ranger = d3_layout_histogramRange, binner = d3_layout_histogramBinSturges;

		function histogram(data, i) {
			var bins = [], values = data.map(valuer, this), range = ranger.call(this, values, i), thresholds = binner.call(this, range, values, i), bin, i = -1, n = values.length, m = thresholds.length - 1, k = frequency ? 1 : 1 / n, x;

			// Initialize the bins.
			while(++i < m) {
				bin = bins[i] = [];
				bin.dx = thresholds[i + 1] - (bin.x = thresholds[i]);
				bin.y = 0;
			}

			// Fill the bins, ignoring values outside the range.
			i = -1;
			while(++i < n) {
				x = values[i];
				if((x >= range[0]) && (x <= range[1])) {
					bin = bins[d3.bisect(thresholds, x, 1, m) - 1];
					bin.y += k;
					bin.push(data[i]);
				}
			}

			return bins;
		}

		// Specifies how to extract a value from the associated data. The default
		// value function is `Number`, which is equivalent to the identity function.
		histogram.value = function(x) {
			if(!arguments.length)
				return valuer;
			valuer = x;
			return histogram;
		};
		// Specifies the range of the histogram. Values outside the specified range
		// will be ignored. The argument `x` may be specified either as a two-element
		// array representing the minimum and maximum value of the range, or as a
		// function that returns the range given the array of values and the current
		// index `i`. The default range is the extent (minimum and maximum) of the
		// values.
		histogram.range = function(x) {
			if(!arguments.length)
				return ranger;
			ranger = d3.functor(x);
			return histogram;
		};
		// Specifies how to bin values in the histogram. The argument `x` may be
		// specified as a number, in which case the range of values will be split
		// uniformly into the given number of bins. Or, `x` may be an array of
		// threshold values, defining the bins; the specified array must contain the
		// rightmost (upper) value, thus specifying n + 1 values for n bins. Or, `x`
		// may be a function which is evaluated, being passed the range, the array of
		// values, and the current index `i`, returning an array of thresholds. The
		// default bin function will divide the values into uniform bins using
		// Sturges' formula.
		histogram.bins = function(x) {
			if(!arguments.length)
				return binner;
			binner = typeof x === "number" ? function(range) {
				return d3_layout_histogramBinFixed(range, x);
			} : d3.functor(x);
			return histogram;
		};
		// Specifies whether the histogram's `y` value is a count (frequency) or a
		// probability (density). The default value is true.
		histogram.frequency = function(x) {
			if(!arguments.length)
				return frequency;
			frequency = !!x;
			return histogram;
		};
		return histogram;
	};
	function d3_layout_histogramBinSturges(range, values) {
		return d3_layout_histogramBinFixed(range, Math.ceil(Math.log(values.length) / Math.LN2 + 1));
	}

	function d3_layout_histogramBinFixed(range, n) {
		var x = -1, b = +range[0], m = (range[1] - b) / n, f = [];
		while(++x <= n)
		f[x] = m * x + b;
		return f;
	}

	function d3_layout_histogramRange(values) {
		return [d3.min(values), d3.max(values)];
	}


	d3.layout.hierarchy = function() {
		var sort = d3_layout_hierarchySort, children = d3_layout_hierarchyChildren, value = d3_layout_hierarchyValue;

		// Recursively compute the node depth and value.
		// Also converts the data representation into a standard hierarchy structure.
		function recurse(data, depth, nodes) {
			var childs = children.call(hierarchy, data, depth), node = d3_layout_hierarchyInline ? data : {
				data : data
			};
			node.depth = depth;
			nodes.push(node);
			if(childs && ( n = childs.length)) {
				var i = -1, n, c = node.children = [], v = 0, j = depth + 1;
				while(++i < n) {
					d = recurse(childs[i], j, nodes);
					d.parent = node;
					c.push(d);
					v += d.value;
				}
				if(sort)
					c.sort(sort);
				if(value)
					node.value = v;
			} else if(value) {
				node.value = +value.call(hierarchy, data, depth) || 0;
			}
			return node;
		}

		// Recursively re-evaluates the node value.
		function revalue(node, depth) {
			var children = node.children, v = 0;
			if(children && ( n = children.length)) {
				var i = -1, n, j = depth + 1;
				while(++i < n)
				v += revalue(children[i], j);
			} else if(value) {
				v = +value.call(hierarchy, d3_layout_hierarchyInline ? node : node.data, depth) || 0;
			}
			if(value)
				node.value = v;
			return v;
		}

		function hierarchy(d) {
			var nodes = [];
			recurse(d, 0, nodes);
			return nodes;
		}


		hierarchy.sort = function(x) {
			if(!arguments.length)
				return sort;
			sort = x;
			return hierarchy;
		};

		hierarchy.children = function(x) {
			if(!arguments.length)
				return children;
			children = x;
			return hierarchy;
		};

		hierarchy.value = function(x) {
			if(!arguments.length)
				return value;
			value = x;
			return hierarchy;
		};
		// Re-evaluates the `value` property for the specified hierarchy.
		hierarchy.revalue = function(root) {
			revalue(root, 0);
			return root;
		};
		return hierarchy;
	};
	// A method assignment helper for hierarchy subclasses.
	function d3_layout_hierarchyRebind(object, hierarchy) {
		d3.rebind(object, hierarchy, "sort", "children", "value");

		// Add an alias for links, for convenience.
		object.links = d3_layout_hierarchyLinks;

		// If the new API is used, enabling inlining.
		object.nodes = function(d) {
			d3_layout_hierarchyInline = true;
			return (object.nodes = object)(d);
		};
		return object;
	}

	function d3_layout_hierarchyChildren(d) {
		return d.children;
	}

	function d3_layout_hierarchyValue(d) {
		return d.value;
	}

	function d3_layout_hierarchySort(a, b) {
		return b.value - a.value;
	}

	// Returns an array source+target objects for the specified nodes.
	function d3_layout_hierarchyLinks(nodes) {
		return d3.merge(nodes.map(function(parent) {
			return (parent.children || []).map(function(child) {
				return {
					source : parent,
					target : child
				};
			});
		}));
	}

	// For backwards-compatibility, don't enable inlining by default.
	var d3_layout_hierarchyInline = false;
	d3.layout.pack = function() {
		var hierarchy = d3.layout.hierarchy().sort(d3_layout_packSort), size = [1, 1];

		function pack(d, i) {
			var nodes = hierarchy.call(this, d, i), root = nodes[0];

			// Recursively compute the layout.
			root.x = 0;
			root.y = 0;
			d3_layout_packTree(root);

			// Scale the layout to fit the requested size.
			var w = size[0], h = size[1], k = 1 / Math.max(2 * root.r / w, 2 * root.r / h);
			d3_layout_packTransform(root, w / 2, h / 2, k);

			return nodes;
		}


		pack.size = function(x) {
			if(!arguments.length)
				return size;
			size = x;
			return pack;
		};
		return d3_layout_hierarchyRebind(pack, hierarchy);
	};
	function d3_layout_packSort(a, b) {
		return a.value - b.value;
	}

	function d3_layout_packInsert(a, b) {
		var c = a._pack_next;
		a._pack_next = b;
		b._pack_prev = a;
		b._pack_next = c;
		c._pack_prev = b;
	}

	function d3_layout_packSplice(a, b) {
		a._pack_next = b;
		b._pack_prev = a;
	}

	function d3_layout_packIntersects(a, b) {
		var dx = b.x - a.x, dy = b.y - a.y, dr = a.r + b.r;
		return (dr * dr - dx * dx - dy * dy) > .001;
		// within epsilon
	}

	function d3_layout_packCircle(nodes) {
		var xMin = Infinity, xMax = -Infinity, yMin = Infinity, yMax = -Infinity, n = nodes.length, a, b, c, j, k;

		function bound(node) {
			xMin = Math.min(node.x - node.r, xMin);
			xMax = Math.max(node.x + node.r, xMax);
			yMin = Math.min(node.y - node.r, yMin);
			yMax = Math.max(node.y + node.r, yMax);
		}

		// Create node links.
		nodes.forEach(d3_layout_packLink);

		// Create first node.
		a = nodes[0];
		a.x = -a.r;
		a.y = 0;
		bound(a);

		// Create second node.
		if(n > 1) {
			b = nodes[1];
			b.x = b.r;
			b.y = 0;
			bound(b);

			// Create third node and build chain.
			if(n > 2) {
				c = nodes[2];
				d3_layout_packPlace(a, b, c);
				bound(c);
				d3_layout_packInsert(a, c);
				a._pack_prev = c;
				d3_layout_packInsert(c, b);
				b = a._pack_next;

				// Now iterate through the rest.
				for(var i = 3; i < n; i++) {
					d3_layout_packPlace(a, b, c = nodes[i]);

					// Search for the closest intersection.
					var isect = 0, s1 = 1, s2 = 1;
					for( j = b._pack_next; j !== b; j = j._pack_next, s1++) {
						if(d3_layout_packIntersects(j, c)) {
							isect = 1;
							break;
						}
					}
					if(isect == 1) {
						for( k = a._pack_prev; k !== j._pack_prev; k = k._pack_prev, s2++) {
							if(d3_layout_packIntersects(k, c)) {
								if(s2 < s1) {
									isect = -1;
									j = k;
								}
								break;
							}
						}
					}

					// Update node chain.
					if(isect == 0) {
						d3_layout_packInsert(a, c);
						b = c;
						bound(c);
					} else if(isect > 0) {
						d3_layout_packSplice(a, j);
						b = j;
						i--;
					} else {// isect < 0
						d3_layout_packSplice(j, b);
						a = j;
						i--;
					}
				}
			}
		}

		// Re-center the circles and return the encompassing radius.
		var cx = (xMin + xMax) / 2, cy = (yMin + yMax) / 2, cr = 0;
		for(var i = 0; i < n; i++) {
			var node = nodes[i];
			node.x -= cx;
			node.y -= cy;
			cr = Math.max(cr, node.r + Math.sqrt(node.x * node.x + node.y * node.y));
		}

		// Remove node links.
		nodes.forEach(d3_layout_packUnlink);

		return cr;
	}

	function d3_layout_packLink(node) {
		node._pack_next = node._pack_prev = node;
	}

	function d3_layout_packUnlink(node) {
		delete node._pack_next;
		delete node._pack_prev;
	}

	function d3_layout_packTree(node) {
		var children = node.children;
		if(children && children.length) {
			children.forEach(d3_layout_packTree);
			node.r = d3_layout_packCircle(children);
		} else {
			node.r = Math.sqrt(node.value);
		}
	}

	function d3_layout_packTransform(node, x, y, k) {
		var children = node.children;
		node.x = (x += k * node.x);
		node.y = (y += k * node.y);
		node.r *= k;
		if(children) {
			var i = -1, n = children.length;
			while(++i < n)d3_layout_packTransform(children[i], x, y, k);
		}
	}

	function d3_layout_packPlace(a, b, c) {
		var db = a.r + c.r, dx = b.x - a.x, dy = b.y - a.y;
		if(db && (dx || dy)) {
			var da = b.r + c.r, dc = Math.sqrt(dx * dx + dy * dy), cos = Math.max(-1, Math.min(1, (db * db + dc * dc - da * da) / (2 * db * dc))), theta = Math.acos(cos), x = cos * (db /= dc), y = Math.sin(theta) * db;
			c.x = a.x + x * dx + y * dy;
			c.y = a.y + x * dy - y * dx;
		} else {
			c.x = a.x + db;
			c.y = a.y;
		}
	}

	// Implements a hierarchical layout using the cluster (or dendogram) algorithm.
	d3.layout.cluster = function() {
		var hierarchy = d3.layout.hierarchy().sort(null).value(null), separation = d3_layout_treeSeparation, size = [1, 1];
		// width, height

		function cluster(d, i) {
			var nodes = hierarchy.call(this, d, i), root = nodes[0], previousNode, x = 0, kx, ky;

			// First walk, computing the initial x & y values.
			d3_layout_treeVisitAfter(root, function(node) {
				var children = node.children;
				if(children && children.length) {
					node.x = d3_layout_clusterX(children);
					node.y = d3_layout_clusterY(children);
				} else {
					node.x = previousNode ? x += separation(node, previousNode) : 0;
					node.y = 0;
					previousNode = node;
				}
			});
			// Compute the left-most, right-most, and depth-most nodes for extents.
			var left = d3_layout_clusterLeft(root), right = d3_layout_clusterRight(root), x0 = left.x - separation(left, right) / 2, x1 = right.x + separation(right, left) / 2;

			// Second walk, normalizing x & y to the desired size.
			d3_layout_treeVisitAfter(root, function(node) {
				node.x = (node.x - x0) / (x1 - x0) * size[0];
				node.y = (1 - node.y / root.y) * size[1];
			});
			return nodes;
		}


		cluster.separation = function(x) {
			if(!arguments.length)
				return separation;
			separation = x;
			return cluster;
		};

		cluster.size = function(x) {
			if(!arguments.length)
				return size;
			size = x;
			return cluster;
		};
		return d3_layout_hierarchyRebind(cluster, hierarchy);
	};
	function d3_layout_clusterY(children) {
		return 1 + d3.max(children, function(child) {
			return child.y;
		});
	}

	function d3_layout_clusterX(children) {
		return children.reduce(function(x, child) {
			return x + child.x;
		}, 0) / children.length;
	}

	function d3_layout_clusterLeft(node) {
		var children = node.children;
		return children && children.length ? d3_layout_clusterLeft(children[0]) : node;
	}

	function d3_layout_clusterRight(node) {
		var children = node.children, n;
		return children && ( n = children.length) ? d3_layout_clusterRight(children[n - 1]) : node;
	}

	// Node-link tree diagram using the Reingold-Tilford "tidy" algorithm
	d3.layout.tree = function() {
		var hierarchy = d3.layout.hierarchy().sort(null).value(null), separation = d3_layout_treeSeparation, size = [1, 1];
		// width, height

		function tree(d, i) {
			var nodes = hierarchy.call(this, d, i), root = nodes[0];

			function firstWalk(node, previousSibling) {
				var children = node.children, layout = node._tree;
				if(children && ( n = children.length)) {
					var n, firstChild = children[0], previousChild, ancestor = firstChild, child, i = -1;
					while(++i < n) {
						child = children[i];
						firstWalk(child, previousChild);
						ancestor = apportion(child, previousChild, ancestor);
						previousChild = child;
					}
					d3_layout_treeShift(node);
					var midpoint = .5 * (firstChild._tree.prelim + child._tree.prelim);
					if(previousSibling) {
						layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling);
						layout.mod = layout.prelim - midpoint;
					} else {
						layout.prelim = midpoint;
					}
				} else {
					if(previousSibling) {
						layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling);
					}
				}
			}

			function secondWalk(node, x) {
				node.x = node._tree.prelim + x;
				var children = node.children;
				if(children && ( n = children.length)) {
					var i = -1, n;
					x += node._tree.mod;
					while(++i < n) {
						secondWalk(children[i], x);
					}
				}
			}

			function apportion(node, previousSibling, ancestor) {
				if(previousSibling) {
					var vip = node, vop = node, vim = previousSibling, vom = node.parent.children[0], sip = vip._tree.mod, sop = vop._tree.mod, sim = vim._tree.mod, som = vom._tree.mod, shift;
					while( vim = d3_layout_treeRight(vim), vip = d3_layout_treeLeft(vip), vim && vip) {
						vom = d3_layout_treeLeft(vom);
						vop = d3_layout_treeRight(vop);
						vop._tree.ancestor = node;
						shift = vim._tree.prelim + sim - vip._tree.prelim - sip + separation(vim, vip);
						if(shift > 0) {
							d3_layout_treeMove(d3_layout_treeAncestor(vim, node, ancestor), node, shift);
							sip += shift;
							sop += shift;
						}
						sim += vim._tree.mod;
						sip += vip._tree.mod;
						som += vom._tree.mod;
						sop += vop._tree.mod;
					}
					if(vim && !d3_layout_treeRight(vop)) {
						vop._tree.thread = vim;
						vop._tree.mod += sim - sop;
					}
					if(vip && !d3_layout_treeLeft(vom)) {
						vom._tree.thread = vip;
						vom._tree.mod += sip - som;
						ancestor = node;
					}
				}
				return ancestor;
			}

			// Initialize temporary layout variables.
			d3_layout_treeVisitAfter(root, function(node, previousSibling) {
				node._tree = {
					ancestor : node,
					prelim : 0,
					mod : 0,
					change : 0,
					shift : 0,
					number : previousSibling ? previousSibling._tree.number + 1 : 0
				};
			});
			// Compute the layout using Buchheim et al.'s algorithm.
			firstWalk(root);
			secondWalk(root, -root._tree.prelim);

			// Compute the left-most, right-most, and depth-most nodes for extents.
			var left = d3_layout_treeSearch(root, d3_layout_treeLeftmost), right = d3_layout_treeSearch(root, d3_layout_treeRightmost), deep = d3_layout_treeSearch(root, d3_layout_treeDeepest), x0 = left.x - separation(left, right) / 2, x1 = right.x + separation(right, left) / 2, y1 = deep.depth || 1;

			// Clear temporary layout variables; transform x and y.
			d3_layout_treeVisitAfter(root, function(node) {
				node.x = (node.x - x0) / (x1 - x0) * size[0];
				node.y = node.depth / y1 * size[1];
				delete node._tree;
			});
			return nodes;
		}


		tree.separation = function(x) {
			if(!arguments.length)
				return separation;
			separation = x;
			return tree;
		};

		tree.size = function(x) {
			if(!arguments.length)
				return size;
			size = x;
			return tree;
		};
		return d3_layout_hierarchyRebind(tree, hierarchy);
	};
	function d3_layout_treeSeparation(a, b) {
		return a.parent == b.parent ? 1 : 2;
	}

	// function d3_layout_treeSeparationRadial(a, b) {
	//   return (a.parent == b.parent ? 1 : 2) / a.depth;
	// }

	function d3_layout_treeLeft(node) {
		var children = node.children;
		return children && children.length ? children[0] : node._tree.thread;
	}

	function d3_layout_treeRight(node) {
		var children = node.children, n;
		return children && ( n = children.length) ? children[n - 1] : node._tree.thread;
	}

	function d3_layout_treeSearch(node, compare) {
		var children = node.children;
		if(children && ( n = children.length)) {
			var child, n, i = -1;
			while(++i < n) {
				if(compare( child = d3_layout_treeSearch(children[i], compare), node) > 0) {
					node = child;
				}
			}
		}
		return node;
	}

	function d3_layout_treeRightmost(a, b) {
		return a.x - b.x;
	}

	function d3_layout_treeLeftmost(a, b) {
		return b.x - a.x;
	}

	function d3_layout_treeDeepest(a, b) {
		return a.depth - b.depth;
	}

	function d3_layout_treeVisitAfter(node, callback) {
		function visit(node, previousSibling) {
			var children = node.children;
			if(children && ( n = children.length)) {
				var child, previousChild = null, i = -1, n;
				while(++i < n) {
					child = children[i];
					visit(child, previousChild);
					previousChild = child;
				}
			}
			callback(node, previousSibling);
		}

		visit(node, null);
	}

	function d3_layout_treeShift(node) {
		var shift = 0, change = 0, children = node.children, i = children.length, child;
		while(--i >= 0) {
			child = children[i]._tree;
			child.prelim += shift;
			child.mod += shift;
			shift += child.shift + (change += child.change);
		}
	}

	function d3_layout_treeMove(ancestor, node, shift) {
		ancestor = ancestor._tree;
		node = node._tree;
		var change = shift / (node.number - ancestor.number);
		ancestor.change += change;
		node.change -= change;
		node.shift += shift;
		node.prelim += shift;
		node.mod += shift;
	}

	function d3_layout_treeAncestor(vim, node, ancestor) {
		return vim._tree.ancestor.parent == node.parent ? vim._tree.ancestor : ancestor;
	}

	// Squarified Treemaps by Mark Bruls, Kees Huizing, and Jarke J. van Wijk
	// Modified to support a target aspect ratio by Jeff Heer
	d3.layout.treemap = function() {
		var hierarchy = d3.layout.hierarchy(), round = Math.round, size = [1, 1], // width, height
		padding = null, pad = d3_layout_treemapPadNull, sticky = false, stickies, ratio = 0.5 * (1 + Math.sqrt(5));
		// golden ratio

		// Compute the area for each child based on value & scale.
		function scale(children, k) {
			var i = -1, n = children.length, child, area;
			while(++i < n) {
				area = ( child = children[i]).value * (k < 0 ? 0 : k);
				child.area = isNaN(area) || area <= 0 ? 0 : area;
			}
		}

		// Recursively arranges the specified node's children into squarified rows.
		function squarify(node) {
			var children = node.children;
			if(children && children.length) {
				var rect = pad(node), row = [], remaining = children.slice(), // copy-on-write
				child, best = Infinity, // the best row score so far
				score, // the current row score
				u = Math.min(rect.dx, rect.dy), // initial orientation
				n;
				scale(remaining, rect.dx * rect.dy / node.value);
				row.area = 0;
				while(( n = remaining.length) > 0) {
					row.push( child = remaining[n - 1]);
					row.area += child.area;
					if(( score = worst(row, u)) <= best) {// continue with this orientation
						remaining.pop();
						best = score;
					} else {// abort, and try a different orientation
						row.area -= row.pop().area;
						position(row, u, rect, false);
						u = Math.min(rect.dx, rect.dy);
						row.length = row.area = 0;
						best = Infinity;
					}
				}
				if(row.length) {
					position(row, u, rect, true);
					row.length = row.area = 0;
				}
				children.forEach(squarify);
			}
		}

		// Recursively resizes the specified node's children into existing rows.
		// Preserves the existing layout!
		function stickify(node) {
			var children = node.children;
			if(children && children.length) {
				var rect = pad(node), remaining = children.slice(), // copy-on-write
				child, row = [];
				scale(remaining, rect.dx * rect.dy / node.value);
				row.area = 0;
				while( child = remaining.pop()) {
					row.push(child);
					row.area += child.area;
					if(child.z != null) {
						position(row, child.z ? rect.dx : rect.dy, rect, !remaining.length);
						row.length = row.area = 0;
					}
				}
				children.forEach(stickify);
			}
		}

		// Computes the score for the specified row, as the worst aspect ratio.
		function worst(row, u) {
			var s = row.area, r, rmax = 0, rmin = Infinity, i = -1, n = row.length;
			while(++i < n) {
				if(!( r = row[i].area))
					continue;
				if(r < rmin)
					rmin = r;
				if(r > rmax)
					rmax = r;
			}
			s *= s;
			u *= u;
			return s ? Math.max((u * rmax * ratio) / s, s / (u * rmin * ratio)) : Infinity;
		}

		// Positions the specified row of nodes. Modifies `rect`.
		function position(row, u, rect, flush) {
			var i = -1, n = row.length, x = rect.x, y = rect.y, v = u ? round(row.area / u) : 0, o;
			if(u == rect.dx) {// horizontal subdivision
				if(flush || v > rect.dy)
					v = v ? rect.dy : 0;
				// over+underflow
				while(++i < n) {
					o = row[i];
					o.x = x;
					o.y = y;
					o.dy = v;
					x += o.dx = v ? round(o.area / v) : 0;
				}
				o.z = true;
				o.dx += rect.x + rect.dx - x;
				// rounding error
				rect.y += v;
				rect.dy -= v;
			} else {// vertical subdivision
				if(flush || v > rect.dx)
					v = v ? rect.dx : 0;
				// over+underflow
				while(++i < n) {
					o = row[i];
					o.x = x;
					o.y = y;
					o.dx = v;
					y += o.dy = v ? round(o.area / v) : 0;
				}
				o.z = false;
				o.dy += rect.y + rect.dy - y;
				// rounding error
				rect.x += v;
				rect.dx -= v;
			}
		}

		function treemap(d) {
			var nodes = stickies || hierarchy(d), root = nodes[0];
			root.x = 0;
			root.y = 0;
			root.dx = size[0];
			root.dy = size[1];
			if(stickies)
				hierarchy.revalue(root);
			scale([root], root.dx * root.dy / root.value); ( stickies ? stickify : squarify)(root);
			if(sticky)
				stickies = nodes;
			return nodes;
		}


		treemap.size = function(x) {
			if(!arguments.length)
				return size;
			size = x;
			return treemap;
		};

		treemap.padding = function(x) {
			if(!arguments.length)
				return padding;

			function padFunction(node) {
				var p = x.call(treemap, node, node.depth);
				return p == null ? d3_layout_treemapPadNull(node) : d3_layout_treemapPad(node, typeof p === "number" ? [p, p, p, p] : p);
			}

			function padConstant(node) {
				return d3_layout_treemapPad(node, x);
			}

			var type;
			pad = ( padding = x) == null ? d3_layout_treemapPadNull : ( type = typeof x) === "function" ? padFunction : type === "number" ? ( x = [x, x, x, x], padConstant) : padConstant;
			return treemap;
		};

		treemap.round = function(x) {
			if(!arguments.length)
				return round != Number;
			round = x ? Math.round : Number;
			return treemap;
		};

		treemap.sticky = function(x) {
			if(!arguments.length)
				return sticky;
			sticky = x;
			stickies = null;
			return treemap;
		};

		treemap.ratio = function(x) {
			if(!arguments.length)
				return ratio;
			ratio = x;
			return treemap;
		};
		return d3_layout_hierarchyRebind(treemap, hierarchy);
	};
	function d3_layout_treemapPadNull(node) {
		return {
			x : node.x,
			y : node.y,
			dx : node.dx,
			dy : node.dy
		};
	}

	function d3_layout_treemapPad(node, padding) {
		var x = node.x + padding[3], y = node.y + padding[0], dx = node.dx - padding[1] - padding[3], dy = node.dy - padding[0] - padding[2];
		if(dx < 0) {
			x += dx / 2;
			dx = 0;
		}
		if(dy < 0) {
			y += dy / 2;
			dy = 0;
		}
		return {
			x : x,
			y : y,
			dx : dx,
			dy : dy
		};
	}

})();
